package LeetCode;


import java.lang.reflect.Array;
import java.util.*;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}15:48
 */
public class M1 {//最大的剔除集合
    public static void main(String[] args) {
        int[] arr = {3,3,3,3,5,5,5,2,2,7};
        System.out.println(Test(arr));
    }

    public static int Test(int[] arr){
        // 创建直接寻址表
        int max = arr[0];
        for (int i = 0; i < arr.length;i++){
            max = (max < arr[i]) ? arr[i] : max;
        }
        int len = (max+"").length();
        int[] indexs = new int[(int) Math.pow(10,len)];//桶？  寻址表
        for ( int num:arr){
            indexs[num]++;
        }
        //找到最后一位涉及到右数字添加的
        int lastIndex = 0;
        for (int i = 0; i < indexs.length;i++){
            if (indexs[i]!=0){
                lastIndex = i;
            }
        }
        //排序
        Arrays.sort(indexs,0,lastIndex);
        int arrMidLen = arr.length/2;
        //贪心算法
        for (int i = lastIndex; i >-0 ; i--){
            arrMidLen -= indexs[i];
            if (arrMidLen <= 0)
                return lastIndex - i + 1;
        }
        return -1;
    }
}
